Về lịch sử các lãnh thổ hiện do PNA quản lý trước khi tổ chức này được thành lập, xem Lịch sử Palestine và Lịch sử các lãnh thổ Palestine.

Hiệp định Oslo được ký kết ngày 13 tháng 9 năm 1993 giữa Tổ chức Giải phóng Palestine và Israel. Thoả thuận Gaza–Jericho được ký kết ngày 4 tháng 5 năm 1994 và quy định chi tiết việc thành lập Chính quyền Palestine. Đây là một tổ chức lâm thời được lập ra để quản lý một hình thức hạn chế của việc người Palestine tự quản tại các lãnh thổ Palestine trong giai đoạn 5 năm trong thời gian đó các cuộc đàm phán về vị thế cuối cùng sẽ diễn ra.[15][16][17] Hội đồng Trung ương Palestine, hoạt động thay mặt cho Hội đồng Quốc gia Palestine của Tổ chức Giải phóng Palestine, thực hiện thoả thuận này, biến Chính quyền Dân tộc Palestine trở thành tổ chức chịu trách nhiệm cho Uỷ ban Hành pháp PLO trong một cuộc họp được tổ chức tại Tunis từ 10-11 tháng 10 năm 1993.[18] Cuộc tổng tuyển cử được tổ chức để bầu ra cơ quan lập pháp đầu tiên của nó, Hội đồng Lập pháp Palestine, ngày 20 tháng 1 năm 1996.[18] Thời điểm chấm dứt nhiệm kỳ của tổ chức này là ngày 4 tháng 5 năm 1999, nhưng cuộc bầu cử không được tổ chức vì "tình hình bắt buộc".[18]

Từ khi phong trào Intifada lần thứ hai bắt đầu, Chính quyền Palestine (PA) đã suy yếu cả trong các lãnh thổ Palestine bị chiếm đóng (Dải Gaza và Bờ Tây) và ở nước ngoài. Ariel Sharon và chính quyền George W. Bush từ chối đàm phán với Yasser Arafat, lãnh đạo của Tổ chức Giải phóng Palestine (PLO) và là tổng thống khi đó của PA, người họ cho là tạo ra "một phần vấn đề" (liên quan tới Xung đột Israel-Palestine) và không phải là giải pháp của nó[cần dẫn nguồn] — điều này diễn ra mặc dù Arafat là người đại diện ký kết vào Hiệp định Oslo năm 1993. Tháng 1 năm 2006, Hamas giành chiến thắng trong cuộc bầu cử lập pháp, và vì thế thay thế Đảng Fatah của Arafat trở thành Đảng lãnh đạo nhân dân Palestine.

Israel đã buộc tội Chính quyền Palestine làm ngơ và ngầm tài trợ hành động bạo lực chống lại người Israel.[cần dẫn nguồn] Quan điểm này đã được Hoa Kỳ chính thức chấp nhận vào mùa hè năm 2002,[cần dẫn nguồn] nước này sau đó quyết định cản trở hầu hết các hình thức đàm phán với chính quyền Palestine hiện thời, chờ đợi một sự thay đổi tổ chức mang tính nền tảng. Nhóm chuyên gia cố vấn của Hội đồng Quan hệ Nước ngoài Hoa Kỳ đã tuyên bố Chính quyền Palestine dưới sự lãnh đạo của Arafat là một thiên đường cho Chủ nghĩa khủng bố.[cần dẫn nguồn]

Trong phong trào Intifada, Israel thường nhắm vào các quan chức và các nguồn tài nguyên của Chính quyền Palestine. Đặc biệt, nhiều người đã bị bắt giữ, ám sát hay giết hại khi đang thực thi nhiệm vụ vì cái gọi là các hoạt động khủng bố của họ, những người này đều là các nhân viên của các lực lượng an ninh của Chính quyền Palestine hay chiến binh du kích.[cần dẫn nguồn] Trong Chiến dịch Lá chắn Phòng thủ Israel đã bắt giữ được các tài liệu được cho là bằng chứng rằng Chính quyền Palestine chính thức tài trợ cho các hoạt động khủng bố, được tiến hành bởi các nhân viên của họ như là những công việc "trong bóng tối".[cần dẫn nguồn] Ví dụ, Israel đã bắt giữ và kết án Marwan Barghouti, một lãnh đạo nổi bật của Fatah, vì vai trò lãnh đạo Lữ đoàn các chiến binh tử vì đạo Al-Aqsa. Barghouti vẫn bảo vệ sự vô tội của mình, và bác bỏ sự công bằng của các toà án Israel.

Israel cũng đã nhắm vào cơ sở hạ tầng của Chính quyền Palestine; đặc biệt họ đã đóng cửa nhiều phần cảng biển và cảng hàng không của Palestine, mà Israel coi là đã được sử dụng để vận chuyển những kẻ khủng bố và trang bị của chúng.[cần dẫn nguồn] Những cuộc tấn công của Israel trong thời gian diễn ra phong trào Intifada cũng đã dẫn tới sự huỷ hoại một số cơ sở hạ tầng máy tính của Palestine.

Những động thái này đã bị người Palestine chỉ trích, họ cho rằng Chính quyền Palestine đã ở tình trạng gần sụp đổ, và không còn có khả năng thực thi các nhiệm vụ cả đối nội và đối ngoại. Liên hiệp quốc phản đối khi tuyên bố rằng đó là "một thứ tốt". Điều này bởi những sự xuống cấp thường xuyên của các nguồn tài nguyên và cơ sở hạ tầng của Chính quyền Palestine đã dẫn tới những phàn nàn của PA và một số nhà tài trợ của họ từ Liên minh châu Âu rằng Israel có chủ tâm gây khó khăn cho PA để hạn chế quyền lực của họ trong việc bắt buộc tuân thủ pháp luật nhằm đưa ra một hình ảnh về Chủ nghĩa khủng bố và vô chính phủ tại các lãnh thổ Palestine.[cần dẫn nguồn]

Ngày 7 tháng 7 năm 2004, Nhóm bộ tứ các nhà trung gian hoà giải về Trung Đông đã thông báo cho Ahmed Qurei, Thủ tướng Nhà nước Palestine từ 2003 tới 2006, rằng họ đã "chán ngán và mệt mỏi" với sự thất bại của người Palestine trong việc thực thi những cải cách đã hứa hẹn: "Nếu những cải cách an ninh không được thực hiện, sẽ không có (thêm) sự hỗ trợ quốc tế và không có khoản tiền nào từ cộng đồng thế giới"[19]

Ngày 18 tháng 7 năm 2004, Tổng thống Hoa Kỳ George W. Bush nói rằng việc thành lập một nhà nước Palestine vào cuối năm 2005 dường như vì sự bất ổn và bạo lực trong Chính quyền Palestine.[20]

Để có được một nhà nước Palestine, điều mấu chốt với các lãnh đạo của nó là thái độ cởi mở với cải cách và sự cống hiến với nhân dân.

Vấn đề của người dân Palestine là vấn đề về lãnh thổ - họ không có nhà nước và không có những người lãnh đạo. Người Palestine muốn có sự thay đổi cần yêu cầu thành lập một lực lượng an ninh. Vấn đề thực sự là không có sự lãnh đạo có khả năng nói 'hãy giúp chúng tôi thành lập một nhà nước và chúng tôi sẽ chiến đấu chống khủng bố và đáp ứng các yêu cầu của người dân Palestine'.

Sau cái chết của Arafat ngày 11 tháng 11 năm 2004, Rawhi Fattuh, lãnh đạo Hội đồng Lập pháp Palestine trở thành Tổng thống tạm quyền của Chính quyền Palestine theo Điều 54(2) của Luật Căn bản của Chính quyền.[21]

Nếu chức vụ Tổng thống của Chính quyền Quốc gia bị bỏ trống vì bất kỳ trường hợp nào trong những trường hợp trên, Người phát ngôn Hội đồng Lập pháp Palestine sẽ nắm các quyền lực và trách nhiệm của chức vụ Tổng thống Chính quyền Quốc gia, tạm thời trong một giai đoạn không vượt quá (60) sáu mươi ngày, trong đó cuộc bầu cử tự do và trực tiếp để lựa chọn một tổng thống mới sẽ diễn ra theo Luật Bầu cử Palestine.

Ngày 19 tháng 4 năm 2005, Vladimir Putin tổng thống Nga đồng ý giúp đỡ Chính quyền Palestine khi nói rằng, "Chúng tôi ủng hộ những nỗ lực của Tổng thống Abbas để cải cách lĩnh vực an ninh và chiến đấu chống lại Chủ nghĩa khủng bố [...] Nếu chúng tôi đang chờ đợi Tổng thống Abbas chiến đấu chống lại Chủ nghĩa khủng bố, ông ta không thể làm việc đó với những nguồn tài nguyên mình có hiện tại. [...] Chúng tôi sẽ trao cho Chính quyền Palestine sự giúp đỡ kỹ thuật bằng cách gửi trang bị, huấn luyện nhân viên. Chúng tôi sẽ trao cho Chính quyền Palestine các trực thăng và cả thiết bị viễn thông."[22]

Chính quyền Palestine trở thành chịu trách nhiệm về quản lý dân sự tại một số khu vực nông thôn, cũng như cả về an ninh tại các thành phố lớn ở Bờ Tây và Dải Gaza. Mặc dù giai đoạn lâm thời 5 năm đã kết thúc năm 1999, thoả thuận về vị thế cuối cùng vẫn chưa được ký kết dù có những nỗ lực như Hội nghị thượng đỉnh Trại David năm 2000, Hội nghị thượng đỉnh Taba, và Hiệp định không chính thức Genève.

Tháng 8 năm 2005, Thủ tướng Israel Ariel Sharon bắt đầu đơn phương rút quân của ông khỏi dải Gaza, nhượng lại toàn bộ quyền kiểm soát bên trong Dải Gaza cho Chính quyền Palestine nhưng vẫn giữ quyền kiểm soát các biên giới của nó gồm cả không phận và hải phận (ngoại trừ biên giới với Ai Cập).. Điều này đã làm gia tăng phần trăm lãnh thổ tại dải Gaza nằm dưới quyền quản lý trên danh nghĩa của PNA từ 60% lên 100%.

Cuộc bầu cử lập pháp Palestine diễn ra ngày 25 tháng 1 năm 2006. Hamas giành chiến thắng và Ismail Haniyeh được chỉ định làm Thủ tướng ngày 16 tháng 2 năm 2006 và tuyên thệ nhậm chức ngày 29 tháng 3 năm 2006. Tuy nhiên, khi một chính phủ dưới sự lãnh đạo của Hamas được thành lập, Israel, Hoa Kỳ, Canada, và Liên minh châu Âu ngừng mọi khoản viện trợ cho Chính quyền Palestine, sau khi Hamas từ chối công nhận quyền tồn tại của Israel, từ chối từ bỏ bạo lực, và đồng ý với những thoả thuận trong quá khứ. Những ngước này coi Hamas như một tổ chức khủng bố.

Tháng 12 năm 2006, Ismail Haniyeh, Thủ tướng Chính quyền Palestine tuyên bố rằng PA sẽ không bao giờ công nhận Israel: "Chúng tôi không bao giờ công nhận chính quyền chiếm đoạt Do Thái và sẽ tiếp tục phong trào kiểu jihad của chúng tôi cho tới khi giải phóng được Jerusalem."[23]

Trong một nỗ lực nhằm giải quyết thế bế tắc tài chính và ngoại giao, chính phủ Hamas cùng với Chủ tịch Fatah Mahmoud Abbas đã đồng ý thành lập một chính phủ thống nhất. Haniyeh từ chức ngày 15 tháng 2 năm 2007 như một phần của thoả thuận. Chính phủ thống nhất cuối cùng được hình thành ngày 18 tháng 3 năm 2007 dưới sự lãnh đạo của Thủ tướng Ismail Haniyeh và gồm các thành viên từ Hamas, Fatah và các Đảng cùng các chính trị gia độc lập khác.

Sau khi Hamas chiếm Gaza ngày 14 tháng 6 năm 2007, Chủ tịch Chính quyền Palestine Abbas giải tán chính phủ vào ngày 15 tháng 6 năm 2007 chỉ định Salam Fayad làm Thủ tướng để hình thành một chính phủ mới. Dù quyền lực của chính phủ mới được tuyên bố bao trùm mọi lãnh thổ Palestine, trên thực tế nó bị hạn chế ở những khu vực do Chính quyền Palestine kiểm soát ở Bờ Tây. Chính phủ Fayad đã giành được sự ủng hộ quốc tế. Ai Cập, Jordan, và Ả Rập Xê Út nói vào cuối tháng 6 năm 2007 rằng Chính phủ ở Bờ Tây do Fayad thành lập là chính phủ hợp pháp duy nhất của Palestine, và Ai Cập chuyển đại sứ của họ từ Gaza tới Bờ Tây.[24] Hamas, vốn đã hoàn toàn kiểm soát Dải Gaza, phải đối mặt với sự cô lập ngoại giao và kinh tế của quốc tế.

Một thoả thuận ngừng bắn sáu tháng giữa Hamas và Israel chấm dứt ngày 19 tháng 12 năm 2008.[25][26][27] Hamas tuyên bố rằng Israel phá vỡ thoả thuận ngày 4 tháng 11 năm 2008,[28][29] và rằng Israel đã không dỡ bỏ phong toả Dải Gaza, và Israel cáo buộc Hamas về những vụ bắn tên lửa vào các thị trấn và thành phố miền nam Israel.[30] Cuộc Xung đột Israel-Gaza năm 2008–2009 bắt đầu ngày 27 tháng 12 năm 2008 (11:30 a.m. giờ địa phương; 9:30 a.m. UTC)[31] khi Các lực lượng phòng vệ Israel tung ra một chiến dịch quân sự có mã hiệu Chiến dịch Cast Lead (tiếng Hebrew: מבצע עופרת יצוקה‎, Mivtza Oferet Yetzuka) để trả đũa vụ bắn tên lửa từ khu vực này, nhắm vào các thành viên và cơ sở hạ tầng của Gaza dưới quyền quản lý của Hamas.